/*
提交链接：https://leetcode.cn/problems/word-break/submissions/560802468
139. 单词拆分-中等
完成日期：2024/9/8
线性dp
*/

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        
        // 将单词放进哈希表方便判断
        unordered_set<string> word_set(wordDict.begin(), wordDict.end());
        
        // 统计每个单词长度
        set<int> lens_set;
        for (const string& word : wordDict) {
            lens_set.insert(word.length());
        }
        vector<int> lens(lens_set.begin(), lens_set.end());
        
        vector<bool> f(n + 1, false);
        f[0] = true;
        
        // 从最小长度开始判断是否合适
        int min_len = lens[0];
        for (int i = min_len; i <= n; ++i) {
            if (f[i]) continue;
            for (int len : lens) {
                if (i - len >= 0) {
                    f[i] = f[i] || (f[i - len] && word_set.count(s.substr(i - len, len)));
                }
            }
        }
        return f[n];
    }
};